#include <iostream>
using namespace std;
class MinHeap{
private:
    int *heapArray;
    int CurrentSize;
    int MaxSize;
    void BuildHeap(int n);

public:
    MinHeap(const int n,const int *a);
    virtual ~MinHeap();
    bool isLeaf(int pos) const;
    int leftchild(int pos) const;
    int parent(int pos) const;
    bool Remove(int pos,int & node);
    bool Insert(const int &newNode);
    void RemoveMin(int &min_val);
    void SiftUp(int position);
    void SiftDown(int position);
    void show();
    void sort();
};
MinHeap::MinHeap(const int n,const int *a) {
    CurrentSize = n;
    MaxSize = CurrentSize*2;
    heapArray = new int[MaxSize];
    int i=0;
    for(int i=0;i<n;i++)
        heapArray[i] = a[i];
    BuildHeap(CurrentSize);
}
MinHeap::~MinHeap() {
    delete [] heapArray;
}
void MinHeap::SiftDown(int position) {
    int i = position;
    int j = 2*i+1;
    int temp = heapArray[i];
    //右孩子的索引在最大索引内
    while(j<CurrentSize)
    {
        if(j<CurrentSize-1&&heapArray[j]>heapArray[j+1])
            j++;
        if(temp>heapArray[j])
        {
            heapArray[i] = heapArray[j];
            i = j;
            j = 2*j+1;
        }
        else
            break;
    }
    heapArray[i] = temp;
}
void MinHeap::BuildHeap(int n) {
    CurrentSize = n;
    for(int i=CurrentSize/2-1;i>=0;i--)
    {
        SiftDown(i);
    }
}
void MinHeap::SiftUp(int position) {
    int temppos = position;
    int temp = heapArray[temppos];
    while((temppos>0)&&(heapArray[parent(temppos)]>temp))
    {
        heapArray[temppos] = heapArray[parent(temppos)];
        temppos=parent(temppos);
    }
    heapArray[temppos] = temp;
}
bool MinHeap::Remove(int pos, int &node) {
    if((pos<0)||(pos>=CurrentSize))
        return false;
    int temp = heapArray[pos];
    heapArray[pos] = heapArray[--CurrentSize];
    if(heapArray[parent(pos)]>heapArray[pos])
        SiftUp(pos);
    else
        SiftDown(pos);
    node = temp;
    return true;
}
int MinHeap::parent(int pos) const {
    return pos/2;
}
void MinHeap::RemoveMin(int &min_val) {
    min_val = heapArray[0];
    for(int i=1;i<CurrentSize;i++)
        heapArray[i-1]=heapArray[i];
}
bool MinHeap::isLeaf(int pos) const {
    if(pos*2+1>=CurrentSize)
        return true;
    else
        return false;
}
int MinHeap::leftchild(int pos) const {
    if(pos*2+1<CurrentSize)
        return pos*2+1;
}
bool MinHeap::Insert(const int &newNode) {
    if(CurrentSize == MaxSize)
        return false;
    heapArray[CurrentSize] = newNode;
    SiftUp(CurrentSize);
    CurrentSize++;
}
void MinHeap::show() {
    for(int i=0;i<CurrentSize;i++)
        cout<<heapArray[i]<<" ";
    cout<<"\n";
}
void MinHeap::sort() {
    int min_val;
    for(int i=CurrentSize;i>0;i--)
    {
        BuildHeap(i);
        RemoveMin(min_val);
        cout<<min_val<<" ";
    }
    cout<<"\n";
}
int main()
{
    int a[] = {72,23,5,68,94,16,71,84,76};
    MinHeap m = MinHeap(9,a);
//    m.Insert(63);
//    m.show();
    m.sort();
}